//拓扑排序是对有向无环图(DAG图)的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。
/*
  算法思想：
    1、从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
    2、从网中删除该顶点和所有以它为起点的有向边。
    3、重复操作1和操作2，直到当前AOV网为空或当前网中不存在无前驱的顶点为止。
*/

#include "ALGraph.h" //邻接链表
#include "SqStack.h" //顺序栈
#include <iostream>
#include <memory.h>

using namespace std;

int indegree[MaxVertexNum]; //每个结点当前的入度
int print[MaxVertexNum];    //记录拓扑序列
int count = 0;              //计数器，记录当前已找到的拓扑序列结点个数，也是print数组的栈顶指针
SqStack S;                  //顺序栈，用于记录当前入度为0的结点

//判断该AOV网是否可以进行拓扑排序，并输出拓扑排序序列
bool TopologicalSort(ALGraph G)
{
    InitStack(S);                      //初始化栈，存储当前入度为0的顶点
    for (int i = 0; i < G.vexnum; i++) //遍历所有顶点，将入度为0的顶点入栈
        if (indegree[i] == 0)
            Push(S, i);
    while (!StackEmpty(S)) //若栈不空，则执行循环体
    {
        int i = Pop(S);                                        //栈顶元素出栈并赋值给i
        print[count++] = i;                                    //记录出栈元素
        for (ArcNode *p = G.vertexes[i].first; p; p = p->next) //将所有被结点i指向的结点的入度减1，并将入度为0的结点入栈
        {
            int v = p->adjvex;    //被i结点指向的结点
            if (!(--indegree[v])) //若减完入度后为0，则入栈
                Push(S, v);
        }
    }
    if (count == G.vexnum) //若所有结点都已被拓扑序列记录，返回true，否则返回false
        return true;
    else
        return false;
}

int main()
{
    ALGraph G;
    G.DirStatue = 1; //有向图，且不带权
    cout << "input vexnum and arcnum:\n";
    cin >> G.vexnum >> G.arcnum; //确认该图顶点数和边数
    Init(G);                     //初始化图G

    //得到该AOV网的邻接链表
    cout << "please input (x y):\n";
    for (int x, y, i = 0; i < G.arcnum; ++i)
    {
        cin >> x >> y;
        AddEdge(G, x, y);
    }

    //初始化indegree数组
    for (int i = 0; i < G.vexnum; i++)
    {
        int v = G.vertexes[i].vertex;
        for (ArcNode *p = G.vertexes[v].first; p; p = p->next) //将所有被结点v指向的结点的入度加1
            indegree[p->adjvex]++;
    }

    //初始化print数组全为-1(因为测试样例中有顶点代号为0，为防止冲突，所以这里全部赋值为-1)
    memset(print, -1, sizeof(print));

    //测试代码
    if (TopologicalSort(G))
    {
        cout << "The Topological Sequence is:\n";
        for (int i = 0; i < count; i++)
            cout << print[i] << ' ';
    }
    else
        cout << "ERROR: The AOV network has a loop!";

    return 0;
}